home *** CD-ROM | disk | FTP | other *** search
/ ftp.cs.arizona.edu / ftp.cs.arizona.edu.tar / ftp.cs.arizona.edu / icon / newsgrp / group93b.txt / 000071_icon-group-sender _Tue May 4 03:01:03 1993.msg < prev    next >
Internet Message Format  |  1993-06-16  |  4KB
  1. Received: by cheltenham.cs.arizona.edu; Sun, 9 May 1993 05:55:12 MST
  2. Date: 4 May 93 03:01:03 GMT
  3. From: portal!cup.portal.com!Eric-Amick@uunet.uu.net  (Richard E Amick)
  4. Organization: The Portal System (TM)
  5. Subject: Re: Is this passable code?
  6. Message-Id: <80791@cup.portal.com>
  7. References: <9304260508.AA21290@internal.apple.com>
  8. Sender: icon-group-request@cs.arizona.edu
  9. To: icon-group@cs.arizona.edu
  10. Status: R
  11. Errors-To: icon-group-errors@cs.arizona.edu
  12.  
  13. >>I started using Icon recently, and am impressed with the
  14. >>power of the language. But, since i'm learning on my own and
  15. >>don't have experience with Icon, i don't know if i'm doing
  16. >>things right. Recently i wrote a short program to find
  17. >>anagrams (yeah...) using the unix dictionary. I'd appreciate
  18. >>any comments/suggestions/flames, etc about my programming
  19. >>style and the Icon way.
  20. >
  21. >I did think of a different (simpler, I believe) way of implementing the
  22. >anagram algorithm, using sets.  I don't know if it's better or worse, but
  23. >it does illustrate my particular style for programming in Icon.  Here it
  24. >is, along with an explanation of some of my stylistic choices:
  25. >
  26. >
  27. ># look up anagrams of all the command line arguments in /usr/dict/words
  28. >
  29. >
  30. >procedure main(LArguments)
  31. >
  32. >local   SAnagrams
  33. >local   fWords
  34. >local   sWord
  35. >
  36. >SAnagrams := set()
  37. >
  38. >every insert(SAnagrams, Permute(map(!LArguments)))
  39. >
  40. >fWords := open("/usr/dict/words") |
  41. >        stop("Cannot open /usr/dict/words for reading; aborting.")
  42. >
  43. >while sWord := read(fWords) do {
  44. >        if member(SAnagrams, map(sWord)) then write(sWord)
  45. >}
  46. >
  47. >close(fWords)
  48. >
  49. >
  50. >end
  51. >
  52. >
  53. >procedure Permute(sString)
  54. >
  55. >local   iPos
  56. >
  57. >if 0 = *sString then return sString
  58. >
  59. >suspend sString[iPos := 1 to *sString] ||
  60. >        Permute(sString[1:iPos] || sString[iPos+1:0])
  61. >
  62. >end
  63. >
  64. >
  65. >
  66. [Lots of commentary about code deleted.]
  67. >Variations on this algorithm:  There are 24259 words in /usr/dict/words on
  68. >my Unix machine.  If I was expecting to process many words with 8 or more
  69. >unique letters (8! = 40320 permutations), I would have approached this a
  70. >little differently.  I would have read /usr/dict/words into a set (or a
  71. >table, if I thought that preserving case was important), and do something
  72. >like [note:  if you want to preserve case, it's actually a little harder
  73. >than this.  The algorithm below ignores words in /usr/dict/words that only
  74. >differ by case, and it probably shouldn't]:
  75. >
  76. >
  77. >
  78. >procedure main(LArguments)
  79. >
  80. >local   TWords
  81. >local   fWords
  82. >local   sWord
  83. >
  84. >TWords := table()
  85. >
  86. >fWords := open("/usr/dict/words") |
  87. >        stop("Cannot open /usr/dict/words for reading; aborting.")
  88. >
  89. >while sWord := read(fWords) do TWords[map(sWord)] := sWord
  90. >
  91. >close(fWords)
  92. >
  93. >
  94. >every write(\TWords[Permute(map(!LArguments))])
  95. >
  96. >end
  97. >
  98. >
  99. >
  100. >I would probably even come up with a heuristic that analyses LArguments and
  101. >determines which of the two above variations to call to do the work.
  102. >
  103. >
  104. >I hope this is what you were looking for.  I can't believe I wrote this
  105. >much on a 20 line algorithm. :-)  Comments are appreciated.
  106.  
  107. Allow me to propose a combination of the two which just might be faster.
  108. Since virtually all of the permutations generated will not match
  109. anything, perhaps you should consider the basic principle of anagrams:
  110. all the letters are present in both, just in a different order.  If we
  111. put the letters of a word in a standard order, say, sorted
  112. alphabetically, then the comparison will go much faster; surely sorting
  113. is less work than generating 40,000 permutations.  (Considering that
  114. 10-letter words produce about 4,000,000 permutations, this is a very
  115. reasonable idea.)  Build your table as before, but make the sorted
  116. letters the key and the set of words with the same key the data
  117. associated with it.  I'm still in the novice stage with Icon myself, so
  118. I'll let someone else do the coding. :-)  (The algorithm comes from the
  119. book "Programming Pearls" by Jon Bentley, much as I wish I had thought
  120. of it myself.)
  121. >___
  122. >NEVIN ":-)" LIBER,      Blue Meanie, Macintosh System Software
  123. > email:     nevin@apple.com        paper:  Apple Computer, Inc.
  124. > voice:     (408) 974-MIX1                 2 Infinite Loop, MS: 302-4Q
  125. > AppleLink: BADENOV                        Cupertino, CA 95014
  126.